Parsing a boolean expression¶
Time: O(N); Space: O(N); hard
Return the result of evaluating a given boolean expression, represented as a string.
An expression can either be: * “t”, evaluating to True; * “f”, evaluating to False; * “!(expr)”, evaluating to the logical NOT of the inner expression expr; * “&(expr1,expr2,…)”, evaluating to the logical AND of 2 or more inner expressions expr1, expr2, …; * “|(expr1,expr2,…)”, evaluating to the logical OR of 2 or more inner expressions expr1, expr2, …
Example 1:
Input: expression = “!(f)”
Output: True
Example 2:
Input: expression = “|(f,t)”
Output: True
Example 3:
Input: expression = “&(t,f)”
Output: False
Example 4:
Input: expression = “|(&(t,f,t),!(t))”
Output: False
Constraints:
1 <= len(expression) <= 20000
expression[i] consists of characters in {‘(’, ‘)’, ‘&’, ‘|’, ‘!’, ‘t’, ‘f’, ‘,’}.
expression is a valid expression representing a boolean, as given in the description.
Hints:
Write a function “parse” which calls helper functions “parse_or”, “parse_and”, “parse_not”.
[1]:
class Solution1(object):
"""
Time: O(N)
Space: O(N)
"""
def parseBoolExpr(self, expression):
"""
:type expression: str
:rtype: bool
"""
def parse(expression, i):
if expression[i[0]] not in "&|!":
result = expression[i[0]] == 't'
i[0] += 1
return result
op = expression[i[0]]
i[0] += 2
stk = []
while expression[i[0]] != ')':
if expression[i[0]] == ',':
i[0] += 1
continue
stk.append(parse(expression, i))
i[0] += 1
if op == '&':
return all(stk)
if op == '|':
return any(stk)
return not stk[0]
return parse(expression, [0])
[2]:
s = Solution1()
expression = "!(f)"
assert s.parseBoolExpr(expression) == True
expression = "|(f,t)"
assert s.parseBoolExpr(expression) == True
expression = "&(t,f)"
assert s.parseBoolExpr(expression) == False
expression = "|(&(t,f,t),!(t))"
assert s.parseBoolExpr(expression) == False